JB Advanced Collision Checking Tutorial

 

The objective of this tutorial is to introduce different types of collision checking techniques available, to discuss their possible applications, and to provide working examples. The examples are fully commented and this tutorial explains the logic employed in the more involved routines. Functions and SUBs are used almost exclusively to allow you to copy and paste the collision detecting code into your own programs for further exploration.

 

The intended audience of this tutorial is a programmer who has a working knowledge of JB and is familiar with the JB sprite collision system. It is hoped that new programmers will also derive benefit from the working examples provided.

 

Here is a list of the collision detection functions provided in this tutorial:

 

Many will be familiar with the basic detection functions. I have included them all to be as thorough as possible in the discussion of collision techniques available to you the programmer.  I don’t intend to spend too much time explaining how these familiar functions work, but will comment on how they can be used.

 

Having said that, let’s “dive in” and familiarize our selves with these collision functions.

 

 

Point In Rectangle Function

 

This is the simplest and most familiar of the collision detection functions. I’m sure most of you have used something similar to this code. I know that I’ve performed the check directly in code, but have found that I often had to repeat the same lines of code only with different values. When used as a function it becomes as useful as any other intrinsic function (e.g. COS, INT, SQR, etc…). I can iterate through as many different rectangles as I could possibly wish by storing the rectangle information in an array. Which is exactly what I’ve done in the working example for this function.

 

A very good use of this function immediately comes to mind. What if you have a large number of irregularly shaped areas on screen to check each time the mouse moves? You would quickly bring any collision detection system to a crawl if you checked all of the graphic entities for each mouse movement. The trick is to divide the screen into quadrants, which are in turn sub-divided into quadrants, and so forth until you can detect collisions without any noticeable slowdown in your program.

 

This collision function will be the most used of all the collision functions because it allows you to break down complex or numerous collisions into manageable pieces of code. It’s also one of the fastest to evaluate, because when it come to graphics, faster is always better.

 

Another obvious use would be to create your own GUI (Graphical User Interface) buttons instead of using BMP buttons.

 

(Note: all of the “Point In … shape“ functions are great for interestingly shaped buttons however the “Point In Polygon” function can accommodate especially interesting button shapes.)

 

You can also use “Point In Rectangle” as the basis for a graphical inventory system, or a graphical weapons selection module in a point-n-click RPG.

 

<code>

Function pnr(px, py, x, y, w, h)

'=================================================================

'   Function "Point In Rectangle"

'=================================================================

' This function checks to see if the point (px, py) is within the specified rectangle.

'

' If the point IS inside the rectangle a value of 1 is returned.

'

' If the point IS NOT inside the rectangle a value of 0 (zero) is returned.

'=================================================================

' px = the X coord of the point in question

' py = the Y coord of the point in question

' x = upper  left X coord of rectangle

' y = upper  left Y coord of rectangle

' w =  width of rectangle

' h = height of rectangle

'=================================================================

    pnr = ((px>=x) And (px<=(x+w-1)) And (py>=y) And (py<=(y+h-1)))

End Function

</code>

 

As you can see it’s only one line of code that does the job and has been optimized for maximum speed and efficiency.

 

See “Point In Rectangle.Bas” for an example on how to implement this function.

 

 

Point In Circle Function

 

This function detects when a point is inside the radius of a given circle.

 

<code>

Function pnc(px, py, cx, cy, cr)

'=================================================================

'   Function "Point In Circle"

'=================================================================

' This function checks to see if the point (px, py) is inside the specified circle.

'

' If the point IS inside the circle a value of 1 is returned.

'

' If the point IS NOT inside the circle a value of 0 (zero) is returned.

'=================================================================

' px = the X coord of the point in question

' py = the Y coord of the point in question

' cx = center of circle X coordinate

' cy = center of circle Y coordinate

' cr = circle radius

'

'=================================================================

    'This format is fastest and can be 'inlined' for maximum speed

    pnc = (  ((px-cx)*(px-cx) + (py-cy)*(py-cy)) <= cr*cr  )

 

'=================================================================

    'This format is more readable ... but slightly slower

    'dx2 = (px-cx)*(px-cx)

    'dy2 = (py-cy)*(py-cy)

    'r2 = cr * cr

 

    'pnc = ( dx2 + dy2 < r2)

End Function

</code>

 

The detection code has been optimized for maximum speed and efficiency.

 

Run the code “Point In Circle Function.Bas” to get an idea of how to use this function.

 

 

Point In Ellipse Function

 

This function detects when a point is inside of an ellipse.

 

<code>

Function pne(px, py, ex, ey, ew, eh)

'=================================================================

'   Function "Point In Ellipse"

'=================================================================

' This function checks to see if the point (px, py) is inside the specified ellipse.

'

' If the point IS inside the ellipse a value of 1 is returned.

'

' If the point IS NOT inside the ellipse a value of 0 (zero) is returned.

'=================================================================

' px = the X coordinate of the point in question

' py = the Y coordinate of the point in question

' ex = ellipse center X coordinate

' ey = ellipse center Y coordinate

' ew = ellipse width

' eh = ellipse height

'

'=================================================================

    'This format is fastest and can be 'inlined' for maximum speed

    pne = ((px-ex)*(px-ex)/((ew/2)*(ew/2))+(py-ey)*(py-ey)/((eh/2)*(eh/2))<1)

 

'=================================================================

    'This format is more readable ... but slightly slower

    'dx = (px - ex) * (px - ex)

    'dy = (py - ey) * (py - ey)

    'ew2 = (ew/2)*(ew/2)

    'eh2 = (eh/2)*(eh/2)

 

    'pne = (dx/ew2 + dy/eh2 <= 1)

End Function

</code>

 

The detection code has been optimized for maximum speed and efficiency.

 

Run the code “Point In Ellipse Function.Bas” to get an idea of how to use this function.

 

Point In Triangle Function

 

This detects when a point is inside of a triangle.

 

<code>

Function pnt(px,py, x1,y1, x2,y2, x3,y3)

'================================================================='   '  Function "Point In Triangle"

'=================================================================

' This function checks to see if the point (px,py) is within the specified triangle.

'

' If the point IS inside the triangle a value of 1 is returned.

'

' If the point IS NOT inside the triangle a value of 0 (zero) is returned.

'=================================================================

' px = the X coord of the point in question

' py = the Y coord of the point in question

' x1, y1 =  first triangle vertex

' x2, y2 = second triangle vertex

' x3, y3 =  third triangle vertex

'=================================================================

    b0 =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)

    b1 = ((x2 - px) * (y3 - py) - (x3 - px) * (y2 - py)) / b0

    If b1 <= 0 Then pnt = 0 : Exit Function

    b2 = ((x3 - px) * (y1 - py) - (x1 - px) * (y3 - py)) / b0

    If b2 <= 0 Then pnt = 0 : Exit Function

    b3 = ((x1 - px) * (y2 - py) - (x2 - px) * (y1 - py)) / b0

    If b3 <= 0 Then pnt = 0 : Exit Function

    pnt = 1

End Function

</code>

 

The detection code has been optimized for maximum speed and efficiency.

 

Run the code “Point In Triangle Function.Bas” to get an idea of how to use this function.

 

 

Rectangle To Rectangle Collision Function

 

This function checks to see if two rectangles have collided. This is the same collision detection that the JB sprite system uses to detect when sprites have collided. You can use this “Rectangle To Rectangle” collision detection using pictures, boxes, or anything else that is rectangular and doesn’t need transparency.

 

Oh, and it’s also good for “drag and drop” interfaces.

 

<code>

Function r2r(ax, ay, aw, ah, bx, by, bw, bh)

'=================================================================

'   Rectangle To Rectangle Collision Function

'=================================================================

' This function checks to see if two rectangles have collided.

'

' If the rectangles HAVE COLLIDED a non-zero value is returned.

'

' If the rectangles HAVE NOT COLLIDED a value of 0 (zero) is returned.

''=================================================================

' ax = upper  left X coordinate of rectangle "a"

' ay = upper  left Y coordinate of rectangle "a"

' aw =  width of rectangle "a"

' ah = height of rectangle "a"

 

' bx = upper  left X coordinate of rectangle "b"

' by = upper  left Y coordinate of rectangle "b"

' bw =  width of rectangle "b"

' bh = height of rectangle "b"

'

'NOTE: negative coordinate values will return non-valid results.

'=================================================================

    'This format is fastest and can be 'inlined' for maximum speed

    r2r =(((((bx+bw-1)-ax) Xor (bx-(ax+aw-1)))  And _

           ((by-(ay+ah-1)) Xor ((by+bh-1)-ay))) And 2147483648)

'=================================================================

    'This format is more readable... but slightly slower

 

    'ax2 = ax + aw - 1

    'ay2 = ay + ah - 1

    'bx2 = bx + bw - 1

    'by2 = by + by - 1

 

    'a = (bx2 - ax) Xor (bx - ax2)

    'b = (by - ay2) Xor (by2 - ay)

    'c = 2147483648                    'c = &H80000000

    'r2r = (a And b) And c

End Function

</code>

 

The detection code has been optimized for maximum speed and efficiency.

 

Run the code “Rectangle To Rectangle Function.Bas” to get an idea of how to use this function.

 

Circle To Circle Collision Function

 

This function determines when two circles have collided.

 

<code>

Function c2c(ax, ay, ar, bx, by, br)

'=================================================================

'   Circle To Circle Collision Function

'=================================================================

' This function checks to see if the two circles have collided.

'

' If the circles HAVE COLLIDED a value of 1 is returned.

'

' If the circles HAVE NOT COLLIDED a value of 0 (zero) is returned.

'=================================================================

' ax = center X coordinate of circle "a"

' ay = center Y coordinate of circle "a"

' ar = radius of circle "a"

' bx = center X coordinate of circle "b"

' by = center Y coordinate of circle "b"

' br = radius of circle "b"

'=================================================================

    c2c = (((ar + br) * (ar + br)) > ((ax - bx) * (ax - bx) + (ay - by) * (ay - by)))

End Function

</code>

 

The detection code has been optimized for maximum speed and efficiency.

 

Run the code “Point In Triangle Function.bas” to get an idea of how to use this function.

 

Circle To Line Collision

 

This function determines when a circle and a line segment collide. A few possible uses come immediately to mind, such as a bumper pool game, miniature golf game, or a pinball game.

 

<code>

Function c2L(x1, y1, x2, y2, cx, cy, cr)

'=================================================================

' Circle To Line Function

'=================================================================

' This function checks if a circle has collided with a line

'

' c2L returns a 1 if the circle has collided with the line

'

' c2L returns a 0 (zero) if no collision has occurred

'=================================================================

' x1, y1, x2, y2 are the two coordinates defining the line to check

'

' cx, cy are the coordinates of the center of the circle

' cr is the radius of the circle

'=================================================================

 

    d = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)

    If d <> 0 Then d = ((cx - x1) * (x2 - x1) + (cy - y1) * (y2 - y1)) / d

    'Clip To the line segments legal bounds

    If d < 0.0 Then d = 0

    If d > 1.0 Then d = 1

    dx = cx - ( (x2 - x1) * d + x1)

    dy = cy - ( (y2 - y1) * d + y1)

    c2L = (dx * dx + dy * dy <= cr * cr)

End Function

</code>

 

The detection code has been optimized for maximum speed and efficiency.

 

Run the code “Circle To Line Function.Bas” to get an idea of how to use this function.

 

The seven basic collision detection functions are very simple but do not underestimate their usefulness, under the proper circumstances they are the most efficient routines available.

 

It’s always going to be a trade off between ease of use (complexity) and resources (CPU or memory or both), yet the next two collision routines while not quite as simple are still fairly fast.

 

Point In Polygon Function

 

This function detects when a point is on the inside of a user-defined polygon. Since the number of sides of the polygon can be huge, you have a great deal of freedom in creating polygons of just about any shape and size.

 

Up until now, the most we’ve had to deal with is four points as in “Point In Rectangle”. This next function can process a minimum of three points and a practical maximum of 500 points! It’s obvious that we’ll need to come up with a logical procedure for dealing with the entire range of possibilities.

 

This means that we’ll need to store and access every single pair of coordinates that define the polygon, so naturally we’ll have to resort to using an array to store all those coordinates. Another implication is that we’ll need to either store those coordinates in data statements or read them in from a disk file to fill all the elements of the array. Don’t worry it’s all been taken care of, but we’ll need to discuss how it’s all laid out so you can use this function in your own programs.

 

First things first, we must define what a polygon is and is not. Here’s our definition of a polygon:

 

A polygon is a collection of any three or more non-collinear points.

 

Which means you can have points that are collinear as long as at least three of the points that define the polygon are not collinear.

 

This is definitely a case where a picture is worth at least a thousand words.  As illustrated in the figure 1 below, you can create an infinite variety of shapes that meet the requirements of the polygon definition stated above.

 

figure 1

 

The one thing that you’ll want to keep in mind is that the more points required to define the polygon, the more time it will take your computer to display and/or check the polygon. If you only need to display or check one polygon with a large number of vertices (i.e. the point where two sides converge), you shouldn’t notice a significant slow down. However, if you have several polygons with a high number of vertices or hundreds of polygons with a low number of vertices displayed at the same time, you will notice a significant slow down when checking for collisions.

 

Now that we have the definition for a polygon, we’ll need to consider how to utilize an array to store the X-Y coordinate pairs defining a polygon.

 

Let’s start by defining the information required to describe the polygon.

1)     The number of vertices used to define the polygon. This will allow us to use For…Next loops to iterate through the vertices defining the polygon.

2)     The amount of offset in the X and Y directions for the upper-left bounding box corner of the polygon, so that we can locate the polygon anywhere on the screen the same as we do with sprites.

3)     The bounding box’s upper-left corner and the width and height of the bounding box which will allow us to quickly check for collision events even when sprites are not used.

4)     The list of X-Y coordinate pairs locating the vertices of the polygon.

 

In all of the example code I use an array named “poly()”. In describing the details of the polygon storage we’ll use the same array name.

 

To help understand the logic used to populate the poly() array, I refer you to figure 2, which shows all of the required information to define a polygon. In this case the polygon is a triangle to keep things simple.

 

figure 2

         

1)     The number of vertices defining the polygon = 3

2)     The X & Y offsets default to 0,0 (you will locate the polygon in your program as necessary)

3)  The bounding box width is 11 – 0 + 1 = 12     (pixels 0 – 11 inclusive)

The bounding box height is 10 – 0 + 1 = 11    (pixels 0 – 10 inclusive)

4) The list of coordinate pairs are:  0,0    11,10    0,10   (3 pairs of coordinates = 3 vertices)

 

Note: all polygon bounding box upper-left corners are located at 0,0 when they are initially defined so that we can later place them anywhere on screen just as we do with sprites in JB. Please keep this in mind when laying out a polygon in your own program.

 

If you choose not to do so, you will have to hard code the location of your polygon yourself.

 

 

The first array dimension will hold the “index” number of the polygon. This will allow you to access any polygon by index number.

 

Since JB only allows two-dimensional arrays, we will lay out the polygon information as follows:

 

          Index number = 1            ‘since it’s the first polygon defined

 

          poly(1, 0) = 3                  ‘number of vertices

          poly(1, 1) = 0                  ‘X offset     The actual X offset will be determined in your program

          poly(1, 2) = 0                  ‘Y offset     The actual Y offset will be determined in your program

          poly(1, 3) = 12                ‘The bounding box is 12 pixels wide

          poly(1, 4) = 11                ‘The bounding box is 11 pixels tall

          poly(1, 5) = 6                  ‘The X coordinate for vertex 1

          poly(1, 6) = 0                  ‘The Y coordinate for vertex 1

          poly(1, 7) = 11                ‘The X coordinate for vertex 2

          poly(1, 8) = 10                ‘The Y coordinate for vertex 2

          poly(1, 9) = 0                  ‘The X coordinate for vertex 3

          poly(1, 10) = 10               ‘The Y coordinate for vertex 3

         

Note - the total array space required to store a polygon is determined by the following formula:

 

Number of vertices * 2 + 4 = highest array element required in second dimension

 

So we would need to DIM the poly() array as …‘DIM poly(1,10)’     (1 polygon, 3 vertices * 2 + 4 = 10) for the example polygon shown in figure 2.

 

With 20 polygons, and the largest of the 20 polygons having 28 vertices you would need to DIM the poly() array as …’DIM poly(20, 60)    (20 polygons, 28 vertices * 2 + 4 = 60).

 

Here’s the code snippet that loads the polygon data from the example above into the poly() array.

 

<code>

Dim poly(1,10)

numPolys = 1

...

    Restore [polygonData]

    For i = 1 To numPolys

        Read numVerts, locX, locY, wide, high

        poly(i,0) = numVerts

        poly(i,1) = locX

        poly(i,2) = locY

        poly(i,3) = wide

        poly(i,4) = high

 

        For j = 5 To numVerts*2 + 3 Step 2

            Read x, y

            poly(i, j)   = x

            poly(i,j+1) = y

        Next j

    Next I

…

[polygonData]

Data 3          ‘number of vertices

Data 0, 0      ‘locX, locY     ‘use just like you would SpriteXY

Data 12        ‘bounding box width

Data 11        ‘bounding box height

Data 6,0,  11,10,  0,10      ‘the 3 vertex coordinate pairs

</code>

 

That’s all there is to placing the vertices in the poly() array. Obviously you wouldn’t want to have to enter all of the polygon vertices by hand as that would become extremely tedious and prone to error. So I’ve written a very simple “Polygon Editor” (see “Polygon Editor.bas”).

 

That sums up the way we’re going to store the polygon information in the poly() array. At long last we’re ready to implement the “Point In Polygon” function.

 

<code>

Function pnp(idx, x, y)

'===============================================================

'  Function “Point In Polygon”

'===============================================================

' This function checks to see if a point is inside the polygon indicated by ‘idx’.

'

' If the point IS inside the polygon a value of 1 is returned.

'

' If the point IS NOT inside the polygon a value of 0 (zero) is returned.

'===============================================================

' idx – is the index of the polygon coordinates to check

' x, y are the coordinates being checked (in or out of polygon)

'===============================================================

    'lastX is the last X coordinate defining current polygon

    lastX = poly(idx, 0) * 2 + 3     'lastY = poly(idx, 0) * 2 + 4

    'assign X-offset to 'oX

    oX = poly(idx,1)

    'assign X-offset to 'oY

    oY = poly(idx,2)

    'loop through all of the points defining current polygon

    For i = 5 To lastX Step 2

        If i = lastX Then j = 5 Else j = (i+2)

        v1 = (poly(idx, i + 1) + oY) <= y

        v2 = y < (poly(idx, j + 1) + oY)

        v3 = (poly(idx, j + 1) + oY) <= y

        v4 = y < (poly(idx, i + 1) + oY)

        v5 = (( (poly(idx,j   ) + oX)) - (poly(idx, i)+oX)) * (y - (poly(idx, i + 1) + oY))

        v6 = ((poly(idx,j + 1) + oY)) - (poly(idx, i + 1)+oY)

        If v6 = 0.0 then v6 = 0.0001

        v7 = poly(idx, i) + oX

        If (((v1 And v2)) Or (v3 And v4)) And (x < v5 / v6 + v7)) Then pnp = 1 - pnp

    Next i

End Function

</code>

 

For a working example of the “Point In Polygon” function run “Point In Polygon.bas”

 

I’m going to digress slightly by showing you two supporting routines that we may or may not use, but nice to have in our toolbox just the same.

 

One of those routines is a SUB to draw the polygon on screen. This could be used as a stand-alone graphic routine or as tool to visually debug a program that uses polygons in collision detection.

 

<code>

Sub drawPoly  h$, index

'===============================================================

'  Function “Draw A Polygon”

'===============================================================

' This function draws the polygon indicated by ‘index’

'

'===============================================================

' h$ is the string representing the graphics handle used in your program

'

' index – indicates which polygon will be drawn on screen

'===============================================================

          lastX  = poly(index,0) * 2 + 3     ‘lastY would be poly(index, 0) * 2 + 4

          oX = poly(index, 1)           ‘offset X value allows place anywhere on screen

          oY = poly(index, 2)          ‘offset Y value allows place anywhere on screen

          #h$ “Place “;poly(index, 5)+oX;” “;poly(index, 6)+oY

          For i = 7 To  lastX Step 2

                   #h$ “Goto “;poly(index, i)+oX;” “;poly(index, i + 1)+oY

          Next I

          #h$ “Goto “;poly(index,5)+oX;” “;poly(index, 6)+oY

End Sub

</code>

 

Another useful routine would be a SUB for moving a polygon to a new location on screen in much the same way the JB “SpriteXY” command locates sprites.

 

<code>

Sub movePoly index, x, y

'===============================================================

'  Function “Move A Polygon”

'===============================================================

' This function changes the location of where a polygon will be drawn or used on screen.

'

'===============================================================

' index – indicates which of the polygons move

' x, y are the new coordinates where the polygon will be moved

'===============================================================

          poly(index, 1) = x

          poly(index, 2) = y

End Sub

</code>

 

Ok, with that out of the way, let’s get back on track.

 

Now that it’s understood how the “Point In Polygon” function works using the poly() array to store the vertex coordinates, we’re going to extend it’s usefulness by cycling through the coordinates of a small polygon and use the “Point In Polygon” (hereafter referred to as PNP) function to see if it is inside of another (larger) polygon. The result is that we’ll have a “Polygon To Polygon” (hereafter referred to as P2P) collision detection function.

 

The main drawback to the P2P function is that if we exceed a certain number of comparisons per frame of graphics display, we will encounter a slight to significant slow down. What that threshold is will depend on the speed of your CPU and graphics subsystem. It is suggested that you work with a conservative number of vertices and/or comparisons to ensure that a large portion of your intended audience is able to use this type of collision detection code with out noticeable or significant slow down. Another strategy is to use the “Rectangle To Rectangle” collision function to see if the bounding boxes of the two polygons have collided. It’s a very fast function reducing the area of the screen you’ll need to check. If there is a collision, you can then check for a collision using the more computationally intensive P2P function. Utilizing both strategies in tandem will give you the best performance.

 

<code>

Function p2p(index1, index2)

'===============================================================

'  Function “Polygon To Polygon” collision

'===============================================================

' This function checks to see if polygon1 has collided with polygon2.

' Typical usage is to check a polygon with a small number of vertices against a

' polygon with the same or larger number of vertices.

'

' If the polygons have collided a value of 1 is returned.

'

' If the polygons have not collided a value of 0 (zero) is returned.

'

'      ***** Note: This function is dependent upon Point In Polygon Function *****

'===============================================================

' index1 – indicates the first polygon to use for collision checking

' index2 – indicates the second polygon to use for collision checking '===============================================================

          numVerts = poly(index1, 0)        'number of vertices in polygon (index1)

          oX = poly(index1, 1)                  'current X-coordinate offset of polygon (index1)

          oY = poly(index1, 2)                  'current Y-coordinate offset of polygon (index1)

          For i = 5 To numVerts * 2 + 3 Step 2

          p2p = pnp(poly(index1, i) + oX, poly(index1, i+1) + oY, index2)

          If p2p = 1 Then Exit For    'If a vertex is inside polygon (index2) then exit from For…Next loop

          Next i

End Function

</code>

 

The whole reason this tutorial came into being is because of a question asked on the JustBASIC forum (URL – http://justbasic.conforums.com/index.cgi?board=code&action=display&num=1240653153 ). Here’s a paraphrased version of the question: “How do I allow my character sprite to cross a bridge spanning a meandering river and still keep my character sprite from entering the river?” I refer to this question as “flaxen’s dilemma”. (see figure 3 below)

figure 3

 

 

This is a perfect situation to utilize some of the collision techniques we’ve studied; “Rectangle To Rectangle” (R2R), “Point In Polygon” (PNP), and “Polygon To Polygon” (P2P). We just need to make a few preparations before we start coding the solution to “flaxen’s dilemma”.

 

First of all, using the “Polygon Editor”, we’ll trace the character sprite with a polygon that keeps the character sprite from entering the river, and trace both the left and the right sides of the river with polygon boundaries that the character sprite polygon will not cross.

 

After tracing the polygons and pressing the “Save Data” for each of the polygon’s, we need to DIM the poly() array and allot enough memory to store all three polygons.

 

Then we’ll need to read the data statements to load the polygon vertices into the poly() array.

 

Lastly, let’s copy and paste the functions necessary to complete the task.

 

Well, that wraps up this collision tutorial. Here are three tips that summarize the use of these collision functions in your own programs.

 

1) Do all of your calculations outside of the graphics rendering loop whenever possible.

 

2) Minimize the number of collisions you check during each frame of graphics.

 

3)     If there are many collisions to check during each frame of graphics, try to implement a divide and conquer strategy to keep the number of collision checks to a minimum.